package com.github.yangyishe.p600;

/**
 * 560. 和为 K 的子数组
 * https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
 * 已解决，但可利用map的特性，进一步增强速度
 *
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 *
 * 子数组是数组中元素的连续非空序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * 示例 2：
 *
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 2 * 104
 * -1000 <= nums[i] <= 1000
 * -107 <= k <= 107
 */
public class Problem560 {
    public static void main(String[] args) {
        int[] nums=new int[]{1,1,1};
        int k=2;

        Problem560 problem560 = new Problem560();
        int count = problem560.subarraySum(nums, k);
        System.out.println("count = " + count);

    }

    /**
     * 思路：
     * 快慢指针记录子数组的前后边界（均为封闭的，利用数组的连续特性）。
     * 遍历时，记录子数组的和。
     * 如果和与k相等，则要求满足，count+1；
     * 如果和小于k，则索取更多的元素，快指针+1；
     * 如果和大于k，则减少元素，慢指针+1；
     *
     * 如果快指针已经到了边界，仍需+1，则循环跳出；
     * 如果慢指针已经到了边界，仍需+1，则循环跳出。
     *
     * 以上情况仅适用于自然数的情况，故不能用此思路。
     *
     * 暴力破解：
     * 遍历所有的情况，共有len*(len-1)/2种情况需要处理，
     * 时间复杂度为O(n^2)
     *
     *
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        //1. 创建一个表示和的数组
        int[] sums=new int[nums.length];
        int count=0;

        //2. 将和从第1个开始加，加到最后一个，并记录其和
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            sums[i]=sum;
            //3. 比较有无=k的值，有则+1
            if(sum==k){
                count++;
            }
        }

        //4. 从第2个开始，比较有无=k-nums[0]的值，以此类推，直到最后一个
        int compare=k;
        for(int i=0;i<nums.length;i++){
            compare+=nums[i];
            for(int j=i+1;j<sums.length;j++){
                if(compare==sums[j]){
                    count++;
                }
            }
        }

        return count;
    }


}
